import java.util.Arrays;

public class Sort {
    /**
     * 插入排序
     * @param array
     */
    public static void insertSort(int[] array) {
        //外层循环代表排序趟数
        for (int i = 0; i < array.length; i++) {
            int j = i;
            int tmp = array[i];
            //在前i个有序序列中寻找插入位置
            while(j > 0) {
                //从后往前遍历前i个有序序列，如果有序序列中的元素大于当前i所指元素，则往后靠
                if(array[j] >= tmp) {
                    array[j] = array[j - 1];
                }
                j--;
            }
            //找到插入位置之后，将i所指的元素插入到前i个有序序列中
            array[j] = tmp;
        }
        //循环结束之后，整个数组即为有序数组
    }

    /**
     * 选择排序
     * @param array 待排序数组
     */
    public static void selectSort(int[] array) {
        //外层循环代表排序趟数
        for (int i = 0; i < array.length; i++) {
            int index = i;
            int min = array[i];
            //在后 n - i 个元素之中寻找一个最小的元素并记录下标
            for (int j = i; j < array.length; j++) {
                if(array[j] < min) {
                    min = array[j];
                    index = j;
                }
            }
            //交换i所指元素和最小的元素
            swap(array,i,index);
        }
    }

    /**
     * 交换数组的i下标和j下标的元素
     *
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void heapSort(int[] array) {
        //把array数组改造成为大根堆
        int usedSize = array.length;
        createHeap(array);

        //交换堆顶元素和堆底元素
        for (int i = 0;i < array.length;i++) {
            swap(array,0,usedSize - 1);
            usedSize--;
            //将剩下的元素向下调整成为大根堆
            siftDown(array,0,usedSize);
        }

    }

    public static void createHeap(int[] array) {
        int usedSize = array.length;
        //遍历调整为大根堆

        for(int i = (usedSize - 1 - 1)/2;i >= 0;i--) {
            siftDown(array,i,usedSize);
        }

    }

    public static void siftDown(int[] array,int parent,int usedSize) {
         //向下调整为大根堆
         int child = 2 * parent + 1;
        while (child < usedSize) {
            if(child + 1 < usedSize && array[child] < array[child + 1]) {
                child++;
            }

            if(array[child] > array[parent]) {
                swap(array,parent,child);
                parent = child;
                child = 2 * child + 1;
            }else {
                break;
            }
        }
    }

    //希尔排序
    //先对数组中的元素进行分组，每个分组内的元素进行直接插入排序。设置一个间隔gap，初始时gap等于数组长度的一半，每次gap都减半
    public static void ShellSort(int[] array) {
        int gap = array.length / 2;
        while(gap >= 1) {
            Shell(array,gap);
            gap /= 2;
        }
    }

    private static void Shell(int[] array, int gap) {
        //记住直接插入排序是增量为1的希尔排序
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j-=gap ){
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,1,4,1,5,9,2,6};
        ShellSort(array);
        System.out.println(Arrays.toString(array));
    }
}
